package org.laizili.solution.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <a href="https://leetcode-cn.com/problems/array-of-doubled-pairs/">954. 二倍数对数组</a>
 * <p>
 * tags: 排序; 哈希表; 模拟
 * </p>
 */
public class Problem954 {
    private static class Solution {
        //模拟构造二倍数对
        public boolean canReorderDoubled(int[] arr) {
            Map<Integer, Integer> i2c = new HashMap<>();
            Arrays.sort(arr);
            for (int num : arr) {
                int cnt = i2c.getOrDefault(num, 0) + 1;
                i2c.put(num, cnt);
            }
            for (int num : arr) {
                if (i2c.containsKey(num)) {

                    int cnt = i2c.get(num) - 1;
                    if (cnt == 0) {
                        i2c.remove(num); // 整形键的移除
                    } else {
                        i2c.put(num, cnt);
                    }
                    if (i2c.containsKey(num * 2)) {
                        int ocnt = i2c.get(num * 2) - 1;
                        if (ocnt == 0) {
                            i2c.remove(num * 2);
                        } else {
                            i2c.put(num * 2, ocnt);
                        }
                    } else if (num % 2 == 0 && i2c.containsKey(num / 2)) {
                        int ocnt = i2c.get(num / 2) - 1;
                        if (ocnt == 0) {
                            i2c.remove(num / 2);
                        } else {
                            i2c.put(num / 2, ocnt);
                        }
                    } else {
                        return false;
                    }
                }
            }
            return true;
        }
    }

    private static class Solution2 {
        // 较优做法
        // 思路：
        //    按照绝对值对键排序，按绝对值键绝对值从小到大构造二倍数对
        public boolean canReorderDoubled(int[] arr) {
            Map<Integer, Integer> n2c = new HashMap<>();
            for (int num : arr) {
                n2c.put(num, n2c.getOrDefault(num, 0) + 1);
            }
            // 按键绝对值从小到大排序
            final List<Integer> sortedKey = n2c.keySet().stream().sorted(Comparator.comparingInt(Math::abs)).collect(Collectors.toList());
            for (int num : sortedKey) {
                int n1 = n2c.getOrDefault(num, 0);
                int n2 = n2c.getOrDefault(2 * num, 0);
                if (n1 > n2) {
                    return false;
                }
                n2c.put(2 * num, n2 - n1);
            }
            return true;
        }
    }
}
